package com.gorkr.labuladong.data_struct.stack;


import java.util.Stack;

/**
 * @author gorkr
 * @date 2022/06/03 09:25
 **/
public class M503NextGreaterElementII {

    public int[] nextGreaterElements(int[] nums) {
        int n = nums.length;
        int[] res = new int[n];
        int[] doubleNums = new int[2 * n];
        for (int i = 0; i < n; i++) {
            doubleNums[i] = nums[i];
            doubleNums[i + n] = nums[i];
        }
        int[] doubleRes = new int[2 * n];

        Stack<Integer> stack = new Stack<>();

        // 拼接两个
        for (int i = doubleNums.length - 1; i >= 0; i--) {
            while (!stack.isEmpty() && stack.peek() <= doubleNums[i]) {
                stack.pop();
            }
            doubleRes[i] = stack.isEmpty() ? -1 : stack.peek();
            stack.push(doubleNums[i]);
        }

        for (int i = 0; i < res.length; i++) {
            res[i] = doubleRes[i];
        }
        return res;


    }
}
    